package leetcode.treeCode.week3.leetcode_106;

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        int n = inorder.length;
        return build(inorder , postorder , 0 , n-1 , 0 , n-1);

    }
    public TreeNode build (int[] inorder, int[] postorder,
                           int inLeft , int inRight ,
                           int postLeft ,int postRight) {
        if (inLeft > inRight || postLeft > postRight) {
            return null;
        }
        int val = postorder[postRight];
        TreeNode node = new TreeNode(val);
        int index = findIndex(inorder, inLeft, inRight, val);
        node.left = build(inorder , postorder , inLeft , index-1 ,postLeft ,postLeft+index -inLeft -1);
        node.right = build(inorder , postorder , index+1 , inRight , postLeft + index - inLeft , postRight -1);
        return node;
    }
    private int findIndex (int [] arr , int left , int right , int target){
        for (int i = left; i <= right; i++) {
            if (arr[i] == target){
                return i;
            }
        }
        return -1;
    }

}